猜测

Time Limit: 10 Sec Memory Limit: 256 MB

Description

img

Input

img

Output

img

Sample Input

3
　　1 1
　　1 2
　　2 1

Sample Output

3
　　explain:
　　(1,1),(1,1),(2,2)不是一个合法猜测（有相同的格子），因此不管怎么猜总是能全部猜中。

HINT

img

Main idea

给定了若干个标准点，用这些点的横纵坐标分为x集和y集，定义猜点表示从x集和y集中各选一个，不能猜出重复的点，问在所有合法方案中最少包含上述几个标准点。

Solution

我们看到了这道题目，考虑从费用流的方法下手。

我们从S->x集：容量为数字出现次数，费用为0；y集->T：容量为数字出现次数，费用为0；x集->y集：容量为1，若组合成了标准点则费用为1，否则为0。

然后我们这样连边，又由于题目要的是最少包含几个点，那么显然最小费用最大流就是答案了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
using namespace std;

const int ONE = 2000001;
const int INF = 2147483640;

int n,x,y;
int S,T;
int E[1001][1001];
int next[ONE],first[ONE],go[ONE],pas[ONE],Fro[ONE],tot=1;
int from[ONE],q[1000001],dist[200001];
bool vis[ONE];
int tou,wei;
int Ans,w[ONE];
int li[ONE],li_num;

struct power
{
    int x,y;
}a[ONE],time[ONE],Max;

int get()
{
    int res,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

void Add(int u,int v,int liu,int z)
{
    next[++tot]=first[u];   first[u]=tot;   go[tot]=v;  w[tot]=z;   pas[tot]=liu;   Fro[tot]=u;
    next[++tot]=first[v];   first[v]=tot;   go[tot]=u;  w[tot]=-z;  pas[tot]=0;     Fro[tot]=v;
}

int Bfs()
{
    memset(dist,63,sizeof(dist));
    dist[S]=0;  q[1]=S; vis[S]=1;
    tou=0;  wei=1;
    while(tou<wei)
    {
        int u=q[++tou];
        for(int e=first[u];e;e=next[e])
        {
            int v=go[e];
            if(dist[v]>dist[u]+w[e] && pas[e])
            {
                dist[v]=dist[u]+w[e]; from[v]=e;
                if(!vis[v])
                {
                    q[++wei]=v;
                    vis[v]=1;
                }
            }
        }
        vis[u]=0;
    }
    return dist[T]!=dist[T+10];
}

void Deal()
{
    int x=INF;
    for(int e=from[T];e;e=from[Fro[e]]) x=min(x,pas[e]);
    for(int e=from[T];e;e=from[Fro[e]])
    {
        pas[e]-=x;
        pas[e^1]+=x;
        Ans += w[e]*x;
    }
}

int main()
{
    n=get();
    for(int i=1;i<=n;i++)
    {
        a[i].x=get();    a[i].y=get();
        li[++li_num]=a[i].x; li[++li_num]=a[i].y;
    }

    sort(li+1,li+li_num+1);
    li_num = unique(li+1,li+li_num+1) - li - 1;
    S=0;    T=2*li_num+1;

    for(int i=1;i<=n;i++)
    {
        a[i].x = lower_bound(li+1,li+li_num+1, a[i].x) - li;
        a[i].y = lower_bound(li+1,li+li_num+1, a[i].y) - li;
        E[ a[i].x ][ a[i].y ] = 1;
        time[a[i].x].x++;            time[a[i].y].y++;
        Max.x = max(Max.x, a[i].x);    Max.y = max(Max.y, a[i].y);
    }

    for(int i=1;i<=Max.x;i++) if(time[i].x) Add(S,i,time[i].x,0);
    for(int i=1;i<=Max.y;i++) if(time[i].y) Add(i+Max.x,T,time[i].y,0);

    for(int i=1;i<=Max.x;i++)
        if(time[i].x)
            for(int j=1;j<=Max.y;j++)
                if(time[j].y)
                {
                    if(E[i][j]) Add(i,j+Max.x,1,1);
                    else Add(i,j+Max.x,1,0);
                }

    while(Bfs()) Deal();

    printf("%d",Ans);

}